In this paper, we consider the problem of link scheduling in multi-hopwireless networks under general interference constraints. Our goal is to designscheduling schemes that do not use per-flow or per-destination information,maintain a single data queue for each link, and exploit only local information,while guaranteeing throughput optimality. Although the celebrated back-pressurealgorithm maximizes throughput, it requires per-flow or per-destinationinformation. It is usually difficult to obtain and maintain this type ofinformation, especially in large networks, where there are numerous flows.Also, the back-pressure algorithm maintains a complex data structure at eachnode, keeps exchanging queue length information among neighboring nodes, andcommonly results in poor delay performance. In this paper, we proposescheduling schemes that can circumvent these drawbacks and guarantee throughputoptimality. These schemes use either the readily available hop-countinformation or only the local information for each link. We rigorously analyzethe performance of the proposed schemes using fluid limit techniques via aninductive argument and show that they are throughput-optimal. We also conductsimulations to validate our theoretical results in various settings, and showthat the proposed schemes can substantially improve the delay performance inmost scenarios.
展开▼